//<p>给你一个整数数组 <code>nums</code> ，数组中的元素 <strong>互不相同</strong> 。返回该数组所有可能的子集（幂集）。</p>
//
//<p>解集 <strong>不能</strong> 包含重复的子集。你可以按 <strong>任意顺序</strong> 返回解集。</p>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [1,2,3]
//<strong>输出：</strong>[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [0]
//<strong>输出：</strong>[[],[0]]
//</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 <= nums.length <= 10</code></li>
//	<li><code>-10 <= nums[i] <= 10</code></li>
//	<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>
//</ul>
//<div><div>Related Topics</div><div><li>位运算</li><li>数组</li><li>回溯</li></div></div><br><div><li>👍 1651</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 子集
 * @author DY Rising
 * @date 2022-05-26 19:35:58
 */
public class P78_Subsets{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P78_Subsets().new Solution();
        System.out.println(solution.subsets(new int[]{1,2,3}));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //先排序
        Arrays.sort(nums);
        List<List<Integer>> list = df(nums, nums.length - 1);
        list.add(new ArrayList<>());
        return list;
    }

    /**
     * 动态规划，
     * 子问题f(n-1)
     * 父问题f(n) = (f(n-1)+n) + [n]
     * @param nums
     * @return
     */
    public List<List<Integer>> df(int[] nums, int n) {
        if (n == 0) {
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> subList = new ArrayList<>();
            subList.add(nums[n]);
            list.add(subList);
            return list;
        }
        List<List<Integer>> list = df(nums, n - 1);
        int length = list.size();
        for (int i = 0; i < length; i++) {
            List<Integer> newSub = new ArrayList<>(list.get(i));
            newSub.add(nums[n]);
            list.add(newSub);
        }
        List<Integer> subList = new ArrayList<>();
        subList.add(nums[n]);
        list.add(subList);
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
